package LeetCode刷题;

import java.util.HashMap;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-28 10:45
 * @description: Functions of this class is
 * 官方解法：（迭代法）
 *public TreeNode buildTree(int[] preorder, int[] inorder) {
 *     if (preorder.length == 0) {
 *         return null;
 *     }
 *     Stack<TreeNode> roots = new Stack<TreeNode>();
 *     int pre = 0;
 *     int in = 0;
 *     //先序遍历第一个值作为根节点
 *     TreeNode curRoot = new TreeNode(preorder[pre]);
 *     TreeNode root = curRoot;
 *     roots.push(curRoot);
 *     pre++;
 *     //遍历前序遍历的数组
 *     while (pre < preorder.length) {
 *         //出现了当前节点的值和中序遍历数组的值相等，寻找是谁的右子树
 *         if (curRoot.val == inorder[in]) {
 *             //每次进行出栈，实现倒着遍历
 *             while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
 *                 curRoot = roots.peek();
 *                 roots.pop();
 *                 in++;
 *             }
 *             //设为当前的右孩子
 *             curRoot.right = new TreeNode(preorder[pre]);
 *             //更新 curRoot
 *             curRoot = curRoot.right;
 *             roots.push(curRoot);
 *             pre++;
 *         } else {
 *             //否则的话就一直作为左子树
 *             curRoot.left = new TreeNode(preorder[pre]);
 *             curRoot = curRoot.left;
 *             roots.push(curRoot);
 *             pre++;
 *         }
 *     }
 *     return root;
 * }
 * }
 **/
public class No从前序与中序遍历序列构造二叉树 {
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public static void main(String args[]){

    }

    /**
     * 回溯法
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer,Integer> map=new HashMap();//创建一个哈希表，用于每次递归的话,可以通过根节点的值，来找到其索引号
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return pre_mid_createTree(0,preorder.length,preorder,0,inorder.length,inorder,map);
    }
    private static TreeNode pre_mid_createTree(int pStart,int pEnd,int preorder[],int iStart,int iEnd,int inorder[],
                                        HashMap<Integer,Integer> map){
        if(pStart==pEnd){
            return null;//递归到了最后一层了
        }
        int rootVal=preorder[pStart];//先序遍历的第一个节点为根节点
        TreeNode root=new TreeNode(rootVal);
        int rootIndex=map.get(rootVal);//通过根节点的值，在中序遍历中去找到
        int leftNum=rootIndex-iStart;//根据在中序遍历中找到的根节点索引，减去中序遍历开始索引，得到的即为左子树的节点数量

        //开始递归下一层
        root.left=pre_mid_createTree(pStart+1,pStart+1+leftNum,preorder,iStart,rootIndex,inorder,map);
        root.right=pre_mid_createTree(pStart+1+leftNum,pEnd,preorder,rootIndex+1,iEnd,inorder,map);
        return root;
    }

}